As one of the essential components of an internet data transmission system, an IP router (“Internet Protocol”) makes a forwarding decision for an input data packet, i.e. it checks a destination address identifier carried in the packet header and directs it to the next output port or output link through which the data packet should be sent. For example, depending on the destination address identifier of the input data packet, the IP router can direct the data packet to a Next Hop router or an Egress™ port for transmission over a respective output link. In a computer network, the NHRP protocol (“Next Hop Resolution Protocol”) is a protocol which can be used so that a computer sending data to another computer can learn the most direct route to the receiving computer. An Egress™ port is a new type of port used in modern IP routers.
In the following, the routing of data is briefly explained with reference to FIG. 7 which shows the schematic construction of an IP router according to the prior art.
The IP router shown in FIG. 7 comprises an input block 1 which receives a plurality of input data packets over N input links or input ports IN1-INN. The input block 1 serves as an input queue and outputs the received data packets in a “First In First Out” (FIFO) manner. A header extracting block 2 is provided which extracts the packet header from the respective data packet to be transmitted so as to obtain the destination address identifier which is included in the packet header. In addition, the data packet is transferred to an output block 6 which serves as a switch. A routing table 4 stores all possible or available forwarding addresses and the respective output link/port numbers of the router. That is to say the routing table comprises a plurality of entries, each entry corresponding to a respective forwarding address to which a data packet can be forwarded by the IP router. The routing table 4 is generated and updated by a block 5 using routing protocols. In FIG. 7, the routing updates are indicated with reference sign UPD. A routing unit 3 receives the destination address identifier extracted by the header extracting block 2 and uses this destination address identifier as a key for searching for a match in the routing table 4, i.e. the routing unit 3 compares the destination address identifier with every entry corresponding to a respective forwarding address information stored in the routing table 4. If the routing unit 3 finds a correspondence between the destination address identifier and one of the forwarding addresses stored in the routing table 4, the respective output link/port number is transferred to the switch 6, and the switch 6 switches the data packet to a respective one of a plurality of M output links/output ports OUT1-OUTM.
Hence, as long as the routing unit 3 finds a correspondence between the destination address identifier extracted by the header extracting block 2 and at least one of the entries stored in the routing table 4, the respective data packet can be switched to one of the output links OUT1-OUTM. If, however, there is no match for the destination address identifier in the routing table 4, the switch 6 cannot switch the respective data packet to one of the output links, and the data packet cannot be forwarded to its destination.
It is obvious that the cost associated with an IP router of the type shown in FIG. 7 and its performance depend very much on the size of the routing table 4. The routing table 4 consumes silicon area and the look-up procedure consumes time as well as power, especially if the routing table 4 is large.
This problem in particular becomes more and more serious with the fast expansion of internet. The newly introduced IPv6 protocol provides address identifiers comprising 128 bits. Theoretically, for an n-bit destination address identifier, the routing table 4 may have up to 2n entries. Hence, as regards the IPv6 protocol, there is a need for an enormous storing capacity for storing such a large routing table 4. Such a large table size, however, makes the look-up procedure even impractical. Therefore, routing table look-up is regarded as the major bottleneck in today's routers.
The most straightforward method for routing table look-up is to perform a linear searching, i.e. compare the destination address identifier of the input data packet with each entry of the routing table until a correspondence between the address identifier and one of the entries in the routing table is recognized. Although this approach is simple, it is hardly used in actual practice due to its poor performance.
To speed up the look-up procedure, various strategies have been used. The most important ones are the usage of a so-called contents-addressed memory (CAM), the search according to a tree-based data structure, and the usage of so-called hashing strategies. Each of these known strategies has its own advantages and disadvantages. However, all of them are based on a search in the original data domain of the destination address identifier. Thus, all of these strategies require a relatively complex search procedure and a relatively large routing table size.